package com.dmall.play.interview.chapter09;

/**
 * 记忆化搜索
 * @author xiao1.wang
 * @date 2021-01-20 10:07:45
 */
public class Leetcode64V3 {

    private int row, col;
    private Integer[][] dp;

    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        row = grid.length;
        col = grid[0].length;
        dp = new Integer[row][col];
        return backTrack(grid, 0, 0, 0);
    }

    private int backTrack(int[][] grid, int row, int col, int total) {
        if (row == this.row - 1 && col == this.col - 1) {
            return grid[row][col];
        }

        if (row >= this.row || col >= this.col) {
            return 1000;
        }

        if (dp[row][col] != null) {
            return dp[row][col];
        }

        total += grid[row][col];
        int bottom = backTrack(grid, row + 1, col, total);
        int right = backTrack(grid, row, col + 1, total);
        return dp[row][col] = Math.min(bottom, right) + grid[row][col];
    }

    /*public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        row = grid.length;
        col = grid[0].length;
        return backTrack(grid, row - 1, col - 1, 0);
    }

    private int backTrack(int[][] grid, int row, int col, int total) {
        if (row == 0 && col == 0) {
            return grid[row][col];
        }

        if (row < 0 || col < 0) {
            return 1000;
        }
        total += grid[row][col];
        int bottom = backTrack(grid, row - 1, col, total);
        int right = backTrack(grid, row, col - 1, total);
        return Math.min(bottom, right) + grid[row][col];
    }*/

    public static void main(String[] args) {
        Leetcode64V3 leetcode64 = new Leetcode64V3();
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        // int[][] grid = {{1, 2}, {1, 1}};
        System.out.println(leetcode64.minPathSum(grid));
    }
}
